#include <iostream>
#include <stack>
#define lowbit(i) ((i) & (-i))
const int maxn = 100010;
using namespace std;
int c[maxn];
stack<int> s;
//更新x后的所有前缀和
void update(int x, int v)
{
    for (int i = x; i < maxn; i += lowbit(i))
        c[i] += v;
}
//得到x的前缀和
int getsum(int x)
{
    int sum = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        sum += c[i];
    return sum;
}
void PeekMedian()
{
    int left = 1, right = maxn, mid, k = (s.size() + 1) / 2;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (getsum(mid) >= k)
            right = mid;
        else
            left = mid + 1;
    }
    printf("%d\n", left);
}
int main()
{
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for (int i = 0; i < n; i++)
    {
        scanf("%s", str);
        if (str[1] == 'u')
        {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        }
        else if (str[1] == 'o')
        {
            if (!s.empty())
            {
                update(s.top(), -1);
                printf("%d\n", s.top());
                s.pop();
            }
            else
            {
                printf("Invalid\n");
            }
        }
        else
        {
            if (!s.empty())
                PeekMedian();
            else
                printf("Invalid\n");
        }
    }
    return 0;
}